package lc2;
import java.util.*;

import org.junit.Test;
public class Ex224 {
    class Solution {
        public int calculate(String s) {
            if (s.charAt(0) == '+' || s.charAt(0) == '-') {
                s = "0" + s;
            }
            s = s.replaceAll(" ", "");
            s = s.replace("(+","(0+");
            s = s.replace("(-", "(0-");
            s = s.replaceAll("\\-\\-", "+"); 
            s = s.replaceAll("\\+\\-", "-"); 
            s = s.replaceAll("\\-\\+", "-"); 
            s = s.replaceAll("\\+\\+", "+"); 
            int n = s.length();
            char[] cs = s.toCharArray(), cals = new char[n];
            int[] nums = new int[n];
            int ci = -1, ni = -1;
            for (int i = 0; i < n; i++) {
                if (isDigit(cs[i])) {
                    int j = i;
                    int num = 0;
                    while (j < n && isDigit(cs[j])) {
                        num = num * 10 + cs[j] - '0';
                        j++;
                    }
                    nums[++ni] = num;
                    i = j - 1;
                } else if (cs[i] == ')') {
                    while (ci >= 0 && cals[ci] != '(') {
                        char c = cals[ci--];
                        int b = nums[ni--], a = nums[ni--];
                        nums[++ni] = calc(a, b, c);
                    }
                    ci--; //(出栈
                } else if (cs[i] == '(') {
                    cals[++ci] = cs[i];
                } else { //+, -
                    if (ci >= 0 && (cals[ci] == '+' || cals[ci] == '-')) {
                        char c = cals[ci--];
                        int b = nums[ni--], a = nums[ni--];
                        nums[++ni] = calc(a, b, c);
                    }
                    cals[++ci] = cs[i];
                }  
            }
            while (ci >= 0) {
                char c = cals[ci--];
                int b = nums[ni--], a = nums[ni--];
                nums[++ni] = calc(a, b, c);
            }
            return nums[0];
        }
    
        private boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }
    
        private int calc(int a, int b, char c) {
            switch(c) {
                case '+' : return a + b;
                case '-' : return a - b;
                case '*' : return a * b;
                case '/' : return a / b;
            }
            return -1;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.calculate("(1+(4+5+2)-3)+(6+8)"));
    }
}
